package leetcode.p160找出两个链表的第一个公共结点;

import leetcode.ListNode;

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null || headB==null) {
            return null;
        }
        //让两个链表从相同位置开始向后走
        //当遇到结点相同时，即为第一个公共结点
        int countA=getLength(headA);
        int countB=getLength(headB);

        ListNode curA=headA;
        ListNode curB=headB;

        //让两个链表从相同位置开始
        if(countA>countB) {
            for(int i=0;i<countA-countB;i++) {
                curA=curA.next;
            }
        }else {
            for(int i=0;i<countB-countA;i++) {
                curB=curB.next;
            }
        }

        while (curA!=curB) {
            curA=curA.next;
            curB=curB.next;
        }
        //未进入循环的条件：要么curA==curB，要么都为空
        return curA;

    }

    private int getLength(ListNode headA) {
        int count=0;
        for(ListNode cur=headA;cur!=null;cur=cur.next) {
            count++;
        }
        return count;
    }
}
